#include <stdio.h>
#include <stdbool.h>

 struct ListNode {
      int val;
      struct ListNode *next;
 };

 typedef struct ListNode ListNode;
 
 //删除链表中的指定元素
struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* NewHead = NULL;
    struct ListNode* prev = NewHead;
    struct ListNode* pcur = head;
    while (pcur)
    {
        if (pcur->val == val)
        {
            pcur = pcur->next;
        }
        else
        {
            //新链表为空
            if (NewHead == NULL)
            {
                NewHead = prev = pcur;
            }
            //新链表不为空
            else
            {
                NewHead->next = pcur;
                NewHead = NewHead->next;
            }
            pcur = pcur->next;
        }
    }
    if (NewHead)
    {
        NewHead->next = NULL;
    }
    return prev;
}

//翻转链表(头插法)
struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* NewHead = NULL;
    struct ListNode* prev = head;
    while (prev)
    {
        prev = prev->next;
        head->next = NewHead;
        NewHead = head;
        head = prev;
    }
    return NewHead;
}

struct ListNode* reverseList(struct ListNode* head)
{
    if (head == NULL)
    {
        return head;
    }
    struct ListNode* n1, * n2, * n3;
    n1 = NULL, n2 = head, n3 = n2->next;
    while (n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if (n3)
            n3 = n3->next;
    }
    return n1;
}
//给你单链表的头结点 head ，请你找出并返回链表的中间结点。
//如果有两个中间结点，则返回第二个中间结点。

struct ListNode* middleNode(struct ListNode* head)
{
    int count = 0;
    struct ListNode* prev = head;
    while (prev)
    {
        count++;
        prev = prev->next;
    }
    int num = count / 2;
    while (num--)
    {
        head = head->next;
    }
    return head;
}

//合并有序链表
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    struct ListNode* NewHead = NULL;
    struct ListNode* NewTail = NULL;
    struct ListNode* L1 = list1;
    struct ListNode* L2 = list2;
    if (L1 == NULL)
    {
        return L2;
    }
    else if (L2 == NULL)
    {
        return L1;
    }
    while (L1 && L2)
    {
        if (L1->val < L2->val)
        {
            //L1尾差到新链表中
            if (NewHead == NULL)
            {
                NewHead = NewTail = L1;
            }
            else
            {
                NewTail->next = L1;
                NewTail = NewTail->next;
            }
            L1 = L1->next;
        }
        else
        {
            //L2尾差到新链表中
            if (NewHead == NULL)
            {
                NewHead = NewTail = L2;
            }
            else
            {
                NewTail->next = L2;
                NewTail = NewTail->next;
            }
            L2 = L2->next;
        }
    }
    if (L1)
    {
        NewTail->next = L1;
    }
    else if (L2)
    {
        NewTail->next = L2;
    }

    return NewHead;
}

//倒数第k个结点
int kthToLast(struct ListNode* head, int k)
{
    struct ListNode* NewHead = head;
    struct ListNode* NewTail = head;
    int num = 1, count = 0;
    while (NewTail->next)
    {
        num++;
        NewTail = NewTail->next;
    }
    count = num - k;
    while (count--)
    {
        NewHead = NewHead->next;
    }
    return NewHead->val;
}

//前与后排序
ListNode* partition(ListNode* pHead, int x)
{
    ListNode* LessHead, * LessTail;
    LessHead = LessTail = (ListNode*)malloc(sizeof(ListNode));
    ListNode* GreaterHead, * GreaterTail;
    GreaterHead = GreaterTail = (ListNode*)malloc(sizeof(ListNode));

    ListNode* pcur = pHead;
    while (pcur)
    {
        if (pcur->val < x)
        {
            //尾差到小链表
            LessTail->next = pcur;
            LessTail = LessTail->next;
        }
        else
        {
            //尾差到大链表
            GreaterTail->next = pcur;
            GreaterTail = GreaterTail->next;
        }
        pcur = pcur->next;
    }
    LessTail->next = GreaterHead->next;
    ListNode* ret = LessHead->next;

    GreaterTail->next = NULL;
    free(LessHead);
    free(GreaterHead);
    LessHead = GreaterHead = NULL;
    return ret;
}

//判断链表是不是回文结构
bool chkPalindrome(ListNode* A)
{
    int arr[900] = { 0 };
    ListNode* pcur = A;
    int i = 0;
    while (pcur)
    {
        arr[i++] = pcur->val;
        pcur = pcur->next;
    }
    //i就是结点的个数
    int left = 0;
    int right = i - 1;
    while (left < right)
    {
        if (arr[left] != arr[right])
        {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

//相交链表
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
    struct ListNode* A = headA;
    struct ListNode* B = headB;

    if (A == B)
    {
        return A;
    }
    else
    {
        while (A)
        {
            while (A != B)
            {
                B = B->next;
                if (B == NULL)
                {
                    B = headB;
                    break;
                }
            }
            if (A == B)
            {
                return A;
            }
            A = A->next;
        }
        return NULL;
    }
}

//判断链表是否带环
bool hasCycle(struct ListNode* head)
{
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            return true;
        }
    }
    return false;
}

bool hasCycle(struct ListNode* head)
{
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast && fast->next && fast->next->next)
    {
        slow = slow->next;
        fast = fast->next->next->next;
        if (slow == fast)
        {
            return true;
        }
    }
    return false;
}

//判断是否有环，但是回到第一个环结点
struct ListNode* detectCycle(struct ListNode* head)
{
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            struct ListNode* pcur = head;
            while (pcur != slow)
            {
                slow = slow->next;
                pcur = pcur->next;
            }
            return pcur;
        }
    }
    return NULL;
}

//随机链表的复制
struct Node {
    int val;
    struct Node* next;
    struct Node* random;
    
};

typedef struct Node Node;

Node* buyNode1(int x)
{
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->val = x;
    newNode->next = newNode->random = NULL;
    return newNode;
}

void AddNode1(Node* phead)
{
    Node* pcur = phead;
    while (pcur)
    {
        //创建新节点，尾差到pcur后面
        Node* Next = pcur->next;
        Node* newNode = buyNode1(pcur->val);
        pcur->next = newNode;
        newNode->next = Next;

        pcur = Next;
    }
}

struct Node* copyRandomList(struct Node* head)
{
    if (head == NULL)
    {
        return NULL;
    }
    //原链表上复制结点
    AddNode1(head);
    //置random
    Node* pcur = head;
    while (pcur)
    {
        Node* copy = pcur->next;
        if (pcur->random != NULL)
        {
            copy->random = pcur->random->next;
        }
        pcur = copy->next;
    }
    //断开链表
    pcur = head;
    Node* newHead;
    Node* newTail;
    newHead = newTail = pcur->next;

    while (pcur->next->next)
    {
        pcur = pcur->next->next;
        newTail->next = pcur->next;
        newTail = newTail->next;
    }
    return newHead;
}





int main()
{

	return 0;
}